package tea.fuxiang.demo.algorithm;

import org.junit.After;
import org.junit.Assert;
import org.junit.Before;
import org.junit.Test;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import tea.fuxiang.demo.common.TreeNode;

/**
 * @description: 二叉树遍历
 * @author: zhongyy
 * @date: 2020-04-01 08:40
 **/
public class BinaryTree {

    private TreeNode tree = null;

    private List arrayList = new ArrayList();

    private LinkedList<TreeNode> linkedList = new LinkedList();

    @Before
    public void buildTree() {
        Integer[] arr = new Integer[]{3,9,20,null,null,15,7};
    }

    public static void main(String[] args) {
        LinkedList<Integer> test = new LinkedList();
        test.addFirst(1);
        test.addFirst(2);
        System.out.println(test);

    }

    @Test
    public void test() {

    }

    public List<Integer> inorderTraversal(TreeNode root) {
        return middleOne(root);
    }

    // 使用递归中序遍历方法一
    public List middleOne(TreeNode root) {
        if(null != root.left) {
            middleOne(root.left);
        }
        arrayList.add(root.val);
        if(null != root.right) {
            middleOne(root.right);
        }
        return arrayList;
    }

    // 使用递归中序遍历方法二
    public List middleTwo(TreeNode root) {
        TreeNode cur = root;
        while (null != cur || !linkedList.isEmpty()) {
            while (null != cur) {
                linkedList.push(cur);
                cur = cur.left;
            }
            cur = linkedList.pop();
            arrayList.add(cur.val);
            cur = cur.right;
        }
        return arrayList;
    }

    // 使用递归后序遍历方法一
    public List rightOne(TreeNode root) {

        while (!linkedList.isEmpty()) {
            arrayList.add(linkedList.peekLast());
        }
        return arrayList;
    }
}
